package problems.daily.y2021m7;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author habitplus
 * @since 2021-07-01 10:32
 */
public class T20210701N1 {
    // LCP 07. 传递信息
    public int numWaysByDp(int n, int[][] relation, int k) {
        // 动态规划
        // dp[i][j] 表示经过第 i 轮传到 j 的总次数
        int[][] dp = new int[k+1][n];

        dp[0][0] = 1;
        int st, ed;
        for (int i = 0; i < k; i++) {
            for (int[] re : relation) {
                st = re[0];
                ed = re[1];
                // 说明 从 st 能经过一轮传到 ed
                dp[i+1][ed] += dp[i][st];
            }
        }
        return dp[k][n-1];
    }

    public int numWaysByBfs(int n, int[][] relation, int k) {
        // BFS
        // 转成邻接表存储边集合
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }

        int st, ed;
        for (int[] edge : relation) {
            st = edge[0];
            ed = edge[1];
            adjList.get(st).add(ed);
        }

        Queue<Integer> que = new LinkedList<>();
        que.offer(0);

        while (k > 0 && !que.isEmpty()) {
            k--;
            for (int i = que.size(); i > 0; i--) {
                st = que.poll();
                for (int e : adjList.get(st)) {
                    que.offer(e);
                }
            }
        }

        int cnt = 0;
        while(!que.isEmpty()) {
            if ((ed = que.poll()) == n - 1) {
                cnt++;
            }
        }
        return cnt;
    }
}
